package LearnAlgorithm.g_数学问题;

import java.util.Scanner;

/*
要求(A / B) % 9973,
但由于A很大，我们只给出：
1.	n (n = A % 9973)
2.	(我们给定的A必能被B整除，且gcd(B, 9973) = 1)

数据的第一行是一个T,表示有T组数据
每组数据有两个数n(0 <= n <= 9973)和B(1 <= B <= 10^9)

对应每组数据输出(A / B) % 9973的值

1
87 123456789
6060




(A / B) % 9973 != (A % 9973) / (B % 9973)								不成立
(A / B) % 9973 = A * (对B的，关于模9973的，倒数) % 9973						成立		实在不明白为什么，就死记硬背

B * x ≡ 1 (mod 9973) 等价于 (B * x) % 9973 = 1
x的第一个大于0的特解，就完全能够可以看作是	“(对B的，关于模9973的，倒数)”	这个数。		实在不明白为什么，就死记硬背
  */
public class g除法加取余的典型例子 {
	public static void main(String[] args) {
		try {
			deal();
		} catch (Exception e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		}
	}
	
	public static void deal() throws Exception {
		Scanner scanner = new Scanner(System.in);
		int T = scanner.nextInt();
		for (int i = 0; i < T; i++) {
			int n = scanner.nextInt();
			int B = scanner.nextInt();
			ExtGcd.inverseElement(B, 9973);
			long x = ExtGcd.x;
			System.out.println((x * n) % 9973);//x * n = x * A % 9973；(x * n) % 9973是为了防止结果过大
		}
	}
	
	public static class ExtGcd {
		static long x;
		static long y;
		public static long gcdEx(long a, long b) {
			if (b == 0) {
				x = 1;
				y = 0;
				return a;
			}
			long res = gcdEx(b, a % b);
			long x1 = x;
			x = y;
			y = x1 - a / b * y;
			return res;
		}
		public static long linearEquation(long a, long b, long m) throws Exception {
			long d = gcdEx(a, b);
			if (m % d != 0) {
				throw new Exception("无解");
			}
			long n = Math.abs(m / d);
			x *= n;
			y *= n;
			return d;
		}
		public static long firstSolution(long a, long b, long m) throws Exception {
			long d = gcdEx(a, b);
			if (m % d != 0) {
				throw new Exception("无解");
			}
			b = b / d;
			x = (x % b + b) % b;
			return x;
		}
		public static long inverseElement(long a, long n) throws Exception {
			long d = linearEquation(a, n, 1);
			x = (x % n + n) % n;
			return d;
		}
	}
}
